#
# @lc app=leetcode.cn id=169 lang=python3
#
# [169] 求众数
#

# @lc code=start
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        def helper(l, r):
            if l == r: return nums[l]
            mid = (l + r) // 2
            left = helper(l, mid)
            right = helper(mid + 1, r)
            if left == right: return left
            left_cnt = sum(1 for i in range(l, r + 1) if nums[i] == left)
            right_cnt = sum(1 for i in range(l, r + 1) if nums[i] == right)
            return left if left_cnt > right_cnt else right
        return helper(0, len(nums) - 1)

# @lc code=end

